Methods for searching suitable paths in a network is a well established discipline with many solved and unsolved problems.
A Shortest Path First (SPF) algorithm, often referred to as the Dijkstra algorithm, is a method commonly used to find the shortest path between nodes in a network. A brief description of this classical problem and of some algorithms which solve it, can be found at the Internet website http://hissa.nist.gov/dads/HTML/shortestpath.html.
Often, it is necessary to find more than one path between a source and a destination. For example, a second path must be found after a failure disrupts a first path. A new path may be computed after a failure has occurred, but in many networks it is desirable to pre-calculate alternate paths before any failure occurs, so that a new path is immediately available in the event of a failure. Furthermore, it is desirable that the alternate path use, as much as possible, different network resources such as nodes and links, than the first path.
Fully disjoint shortest paths between the same source-destination pair are the shortest paths that do not share nodes or links. In real networks, fully disjoint paths may not be possible, and it is desired to find maximally disjoint shortest paths.
The problem of finding multiple disjoint paths is also a classical problem, but unlike the simple path search, does not have a known efficient (scaleable to large networks) perfect solution.
In U.S. Pat. No. 5,872,773 to Katzela et al. is disclosed a heuristic method for determining disjoint routing trees providing maximally disjoint paths in a cellular network. This method is based on destination rooted trees, suitable for cellular networks.
An algorithm for computing shortest and widest maximally disjoint paths is reported in a conference paper by R. Ogier, B. Bellur, and N. Taft-Plotkin entitled “An Efficient Algorithm for Computing Shortest and Widest Maximally Disjoint Paths”, SRI International Technical Report ITAD-1616-TR-170, November 1998. This method in turn is based upon an algorithm by J. W. Suurballe and R. E. Tarjan “A Quick Method for Finding Shortest Pairs of Disjoint Paths”, published in Networks, 14, 1984. The disadvantages of this method are found to be the following:                All paths are pre-computed in advance of setup requests;        The algorithm only finds 2 disjoint path pairs;        The algorithm determines all disjoint path pairs from a source to all destinations (in tree format);        All paths are computed upon every receipt of a QoS (Quality of Service) message update.        
The algorithm is based on a modified Suurballe/Tarjan algorithm for disjoint paths, and, overall, is complex, memory and computationally expensive.
Below is provided a brief description of this algorithm.
    Phase 1: Compute all Max Bandwidth disjoint path pairs from source to all destinations;    Phase 2: Transform Bandwidth/Cost of each link not used in the original tree;    Phase 3: Each node has five variables used in complex calculations;    Phase 4: Get the two paths from the resulting network, mark all links as unmarked, and then traverse the network topology (or graph).
With four complex phases, this algorithm is difficult to implement in software and to maintain in operation.
An extensive discussion of the general problem of finding multiple disjoint paths, and a proposed “split-node” solution to it, can be found in the text book “Survivable Networks: Algorithms for Diverse Routing” by Dr. Ramesh Bhandari, Kluwer Academic Publishers, 1999. This book contains detailed algorithms for calculating disjoint pairs of paths, maximally disjoint paths if full diversity does not exist, and K (K greater than 2) disjoint paths.
While the “split-node” method generates a solution to the problem, it requires a network transformation, in which many nodes are split (i.e. a single node is represented by two nodes), resulting in inefficiency in path computation for a large network.
Accordingly, there is a need in industry for the development of an alternative method, which would provide efficient and reliable generation of multiple maximally disjoint shortest paths in a network and would avoid the above mentioned drawbacks.